package base.sort;


import java.util.Arrays;


//归并排序的非递归写法
public class MergeSort2 {


    public static void mergeSort(int[] arr) {
        int n = arr.length;
        for (int width = 1; width < n; width <<= 1) {
            int l = 0;
            int mid = l + width - 1;
            int r = mid + width;
            while (r < n) {
                merge(arr, l, mid, r);
                l = r + 1;
                mid = l + width - 1;
                r = mid + width;
            }
            if (l < n && mid < n) {
                merge(arr, l, mid, n - 1);
            }
        }
    }

    private static void merge(int[] arr, int l, int mid, int r) {

        int[] tmpArr = new int[r - l + 1];
        int idx = 0;
        int i = l;
        int j = mid + 1;
        while (i <= mid && j <= r) {
            if (arr[i] <= arr[j]) tmpArr[idx++] = arr[i++];
            else tmpArr[idx++] = arr[j++];
        }
        while (i <= mid) tmpArr[idx++] = arr[i++];
        while (j <= r)   tmpArr[idx++] = arr[j++];
        for (int k = 0; k < tmpArr.length; k++) {
            arr[l + k] = tmpArr[k];
        }
    }

    public static void main(String[] args) {

        int[] arr = {4,2,22,3,123,11,2,1,0,2282,21,4343,111,33};
        mergeSort(arr);
        Arrays.stream(arr).forEach(System.out::println);



    }
}
